package hwThree2;

import edu.princeton.cs.algs4.BST;
import edu.princeton.cs.algs4.StdOut;

public class NoneRecurseMethod<Key extends Comparable<Key>, Value> {
    private Node root;             // root of BST

    private class Node {
        private Key key;           // sorted by key
        private Value val;         // associated data
        private Node left, right;  // left and right subtrees
        private int size;          // number of nodes in subtree

        public Node(Key key, Value val, int size) {
            this.key = key;
            this.val = val;
            this.size = size;
        }

        public Value get(Key key) {
            Node current = root;
            while(current != null) {
                int cmp = key.compareTo(key);
                if (cmp == 0) {
                    return current.val;
                } else if (cmp < 0) {
                    current = current.right;
                } else if (cmp > 0) {
                    current = current.left;
                }
            }
            return null;
        }

        public void put(Key key, Value val) {
            if (key == null) throw new IllegalArgumentException("calls put() with a null key");
            if (val == null) {
                return;
            }
            Node newNode = new Node(key, val, 1); // 创建新节点
            if (root == null) { // 如果树为空，直接插入到根节点
                root = newNode;
                return;
            }

            Node parent = null; // 用于记录当前节点的父节点
            Node current = root; // 从根节点开始查找
            while(current != null) {
                parent = current; // 更新父节点
                int cmp = key.compareTo(key);
                if (cmp == 0) {
                    current.val = val;
                    return;
                } else if (cmp < 0) {
                    current = current.right;
                } else if (cmp > 0) {
                    current = current.left;
                }
            }

            // 找到插入位置，根据比较结果挂在父节点的左或右子树上
            int cmp = key.compareTo(parent.key);
            if (cmp < 0) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
            // 从根节点重新更新所有相关节点的 size 值
            root = updateSizes(root);
        }
        public int size() {
            return size(root);
        }

        // return number of key-value pairs in BST rooted at x
        private int size(Node x) {
            if (x == null) return 0;
            else return x.size;
        }
        // 更新所有节点的大小信息（以根节点为起点）
        private Node updateSizes(Node x) {
            if (x == null) return null;
            x.size = 1 + size(x.left) + size(x.right);
            x.left = updateSizes(x.left);
            x.right = updateSizes(x.right);
            return x;
        }
    }
    public static void main(String[] args) {
        edu.princeton.cs.algs4.BST<String, Integer> bst = new BST<>();

        // 插入一些键值对到BST中
        bst.put("S", 1);
        bst.put("E", 2);
        bst.put("A", 3);
        bst.put("R", 4);
        bst.put("C", 5);
        bst.put("H", 6);
        bst.put("M", 7);

        StdOut.println("BST初始化完成，包含以下键值对：");
        for (String key : bst.keys()) {
            StdOut.println(key + " -> " + bst.get(key));
        }
    }
}
